package chapter2;


import edu.princeton.cs.algs4.Heap;
import sort.HeapSort;

import java.util.Arrays;

@SuppressWarnings("Unchecked")
public class PriorityQueue<E extends Comparable<E>> {


    private E[] arr;
    private int cap;//容量

    @SuppressWarnings("unchecked")
    public PriorityQueue(int max) {
        cap = 0;//数组容量
        arr = (E[]) new Comparable[max + 1];
    }

    public boolean isEmpty() {
        return cap == 0;
    }

    public int size() {
        return cap;
    }

    /**
     * 添加元素
     */
    public void insert(E e) {
        arr[cap] = e;
        swim(cap++);
    }

    public void sort() {
        int n = cap;
        for (int i = n / 2; i >= 0; i--) {
            sink(arr, i, n);
        }
        System.out.println("下沉操作后： "+ Arrays.toString(arr));

        while (n > 0) {
            exch(arr, 0, --n);
            sink(arr, 0, n);
        }
    }

    /**
     * 删除元素 并返回
     * 思路： arr[0]为最大元素，将arr[0]用最后一个元素替换，并将替换后的元素下沉
     *
     * @return
     */
    public E delMax() {
        if (cap == 0) {
            throw new NullPointerException("数组元素为空，无法删除");
        }
        E tmp = arr[0];
        arr[0] = arr[cap];
        arr[cap--] = null;//help GC
        sink(0);
        return tmp;
    }

    private boolean lessThan(int i, int j) {
        return lessThan(arr, i, j);
    }

    private boolean lessThan(E[] arr, int i, int j) {
        if (i >= cap) return false;
        if (j >= cap) return false;
        return arr[i].compareTo(arr[j]) < 0;
    }

    //exchange
    private void exch(int i, int j) {
        exch(arr, i, j);
    }

    //exchange
    private void exch(E[] arr, int i, int j) {
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 上浮操作，如果arr[k]比父节点 arr[k/2]大，交换
     *
     * @param k
     */
    private void swim(int k) {
        int parent;
        while (k > 0 && lessThan(k, parent = k / 2)) {
            exch(k, parent);
            k = parent;
        }
    }

    /**
     * 下沉操作 如果arr[k]比子节点 Min(arr[2k], arr[2k+1]) 大，交换
     *
     * @param k
     */
    private void sink(int k) {
        sink(arr, k, cap);
    }

    private void sink(E[] arr, int k, int n) {
        int child;
        while ((child = 2 * k) <= n) {
            if (child < n && lessThan(arr, child, child + 1)) {
                child++;
            }
            if (!lessThan(k, child)) {
                break;
            }
            exch(arr, k, child);
            k = child;
        }
    }

    public void print() {
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
//        PriorityQueue<Integer> queue = new PriorityQueue<>(20);
//        queue.insert(11);
//        queue.insert(2);
//        queue.insert(4);
//        queue.insert(1);
//        queue.insert(16);
//        queue.insert(30);
//        queue.insert(10);
//        queue.insert(22);
//        queue.insert(31);
//        queue.insert(18);
//        queue.insert(12);
//
//        queue.sort();
////
//        queue.print();

        Integer[] arr = {11, 2, 4, 1, 16, 30, 10, 22, 31, 18, 12};

        HeapSort.sort(arr);

        System.out.println(Arrays.toString(arr));
    }
}
